package algorithm.dynamic;


/**
 * https://leetcode.com/problems/longest-increasing-subsequence/
 * Medium
 *
 * 最长递增子序列
 * p[i] 为第i个数结尾的，包含这个数的最长递增子序列的长度
 * 那么 MaxLen = max(p[1] ... p[n])
 * 维护一个数组，结尾Idx表示当前数组最大值
 *
 * dp[i] 为 以nums[i] 为必选结尾的，递增子序列的最大长度
 * ap[i+1] 就是 dp[0] 到 dp[i] 中nums[i+1] 大于其中最后值的，最大的dp 再加1.
 * 如果都不大于，那么dp[i+1]=1
 *
 *
 * Created by yzy on 2021-03-04 17:32
 */
public class LongestIncreasingSubsequence {

    public static void main(String[] args) {
        int[] arr = new int[]{4,10,4,3,8,9};
        System.out.println(lengthOfLIS(arr));
    }

    /**
     * 动态规划
     * 时间复杂度 O(N^2)
     *
     * 最优解是  O(NlogN) https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
     * @param nums
     * @return
     */
    public static int lengthOfLIS(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int maxLen = 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for(int i=1; i<nums.length; i++){
            int tmpIdx = i-1;
            int currMaxLen = 1;
            while(tmpIdx >= 0){
                int tmpLen = nums[tmpIdx] < nums[i] ? dp[tmpIdx]+1 : 1;
                currMaxLen = currMaxLen > tmpLen ? currMaxLen : tmpLen;
                tmpIdx--;
            }
            dp[i] = currMaxLen;
            maxLen = maxLen > currMaxLen ? maxLen : currMaxLen;
        }
        return maxLen;
    }
}
